package Util;

import java.io.Serializable;

public class Arvore2_3_4<T extends Comparable<T>> implements Serializable {
	
	/**
	 * 
	 */
	private static final long serialVersionUID = -5261007562218580036L;
	Node2_3_4<T> rootNode;
	int ordem;
	private Fila<T> filaVisita = new Fila<T>();
	int qtdNode=0;
	
	public Arvore2_3_4(int ordem)
	{
		if(ordem % 2 != 0)//wrong value
			ordem++;//only par number"						
		this.ordem = ordem;
		rootNode = new Node2_3_4<T>(ordem,true);
	}	
	
	public Node2_3_4<T> getRoot()
	{
		return rootNode;		
	}

	public void insert(T obj)
	{
		if(rootNode.isFull())
		{
			Node2_3_4<T> parent = new Node2_3_4<T>(ordem, rootNode);			
			rootNode = parent;      
			parent.add(obj);			
		}
		else		
			rootNode.add(obj);		
	}
	
	public boolean isThere(T obj)
	{		
		T found = LocalRetrieve(obj);
		if(found != null)
			return true;
		return false;				
	}
	
	private T LocalRetrieve(T obj)
	{
		Node2_3_4<T> node = rootNode;
		while (node != null) 
		{
			double d = node.indexOf(obj);
			int i = (int)d;
			if (i == d)	      
				return node.get(i);	      
			else 	      
				node = node.getChild(i);	      
		}
		return null;
	}
	
	public T retrieve(T obj)
	{
		return LocalRetrieve(obj);				
	}
	
	
	/** Remove target from this Node2_3_4. */
	public void delete(T obj) 
	{
		rootNode.remove(obj);
		if ((rootNode.size() == 1) && (!(rootNode.isLeaf())))
			rootNode = rootNode.getChild(0);
	}
	
	public void Symmetric(Node2_3_4<T> node)
	{
		if(node != null)
		{
			qtdNode++;
			for(int i = 0; i<node.size()-1;i++)
			{
				if(!node.isLeaf())
					Symmetric(node.getChild(i));
				filaVisita.insira(node.get(i));				
			}
			if(!node.isLeaf())
				Symmetric(node.getChild(node.size()-1));
		}
	}
	
	public int lenght()
	{
		Symmetric(rootNode);
		return qtdNode;		
	}
	
	public boolean isEmpty()
	{
		return rootNode == null ? true: false;
	}
	
	public T getFirst()
	{
		filaVisita.limpe();
		Symmetric(rootNode);
		
		if (filaVisita.estaVazia())
			return null;
		else
			return filaVisita.remova();		
	}
	
	public T getNext()
	{
		if (filaVisita.estaVazia())
			return null;
		else
			return filaVisita.remova();
	}
	
	
	//method to make any test
	public void Draw()
	{
		
		
	}
	
}
